package com.zhugang.week03;

import java.util.Stack;

/**
 * @program algorithms
 * @description: sortedStack2
 * @author: chanzhugang
 * @create: 2022/06/04 19:07
 */
public class SortedStack2 {

    Stack<Integer> stack = new Stack<>();
    Stack<Integer> tempStack = new Stack<>();

    /**
     * 栈排序：
     * push：直接操作
     * pop、peek倒腾栈
     */
    public void SortedStack2() {

    }

    public void push(int val) {
        stack.push(val);
    }

    /**
     * A -> B
     * 记录最小值
     * B -> A (排除最小值)
     */
    public void pop() {
        // a出栈压入b时找最小值；b出栈压回a（不是最小值的压回a）
        if (stack.isEmpty()) return;
        int minVal = Integer.MAX_VALUE;
        while (!stack.isEmpty()) {
            Integer val = stack.pop();
            if (val < minVal) {
                minVal = val;
            }
            tempStack.push(val);
        }
        boolean removed = false;
        while (!tempStack.isEmpty()) {
            Integer val = tempStack.pop();
            if (val != minVal || (val == minVal && removed == false)) {
                stack.push(val);
            } else {
                removed = true;
            }
        }
    }

    public int peek() {
        if (stack.isEmpty()) {
            return -1;
        }
        int minVal = Integer.MAX_VALUE;
        while (!stack.isEmpty()) {
            Integer val = stack.pop();
            if (val < minVal) {
                minVal = val;
            }
            tempStack.push(val);
        }

        while (!tempStack.isEmpty()) {
            stack.push(tempStack.pop());
        }
        return minVal;
    }

    public boolean isEmpty() {
        return stack.empty();
    }
}